/**
 * @file KMP.cc
 * @author snow-tyan (zziywang@163.com)
 * @brief {Life is too short to learn cpp.}
 * @version 0.1
 * @date 2021-11-12
 * 
 * @copyright Copyright (c) 2021
 * 
 * 采了两个大坑。。。服啦
 */

#include <iostream>
#include <string>
#include <vector>
using namespace std;

template <class T>
void print(const T &t)
{
    typename T::const_iterator it = t.cbegin();
    for (; it != t.cend(); ++it) {
        cout << *it << " ";
    }
    cout << endl;
}

/***
 * 其实求next数组，相当于模式串t自己和自己匹配，
 * next数组默认next[0]=-1,其余全0
 * 当匹配时才更新当前next[i] = j
 * 不匹配时回退j = next[j]
 * O(N) N是模式串t长度
 * **/
void getNext(string &t, vector<int> &next)
{
    next[0] = -1;
    int j = -1;
    int i = 0;
    // 采坑一：这里next范围应该和i对齐，next[0]被占用了，故i遍历到t.size()-1即可
    while (i < t.size() - 1) {
        if (j == -1) {
            ++i, ++j;
        } else if (t[i] == t[j]) {
            ++i, ++j;
            next[i] = j; // important
        } else {
            j = next[j]; // back j pointer
        }
    }
}

/***
 * 和求next数组不同的是，j从0开始，不必更新next
 * 匹配时往前走，不匹配时回退j = next[j]
 * 当j = t.size()时记录答案i - j
 * **/
vector<int> kmp(string &s, string &t)
{
    int m = s.size(), n = t.size();
    if (n == 0) { // 模式串为空
        return {0};
    }
    if (m < n) { // 模式串比主串还长
        return {-1};
    }
    int i = 0, j = 0;
    vector<int> res;
    vector<int> next(n, 0);
    getNext(t, next);
    while (i < m) {
        if (j == -1 || s[i] == t[j]) {
            ++i, ++j;
            // 采坑二：j可能等于-1，因此最好不要拿无符号整型与其比较
        } else if (j == n) {
            res.push_back(i - j);
            j = next[j];
        } else {
            j = next[j];
        }
    }
    if (j == n) {
        res.push_back(i - j);
    }
    if (!res.empty()) {
        return res;
    }
    return {-1};
}

void testNext(string t)
{
    cout << "模式串t = ";
    print(t);
    vector<int> next(t.size(), 0);
    getNext(t, next);
    cout << "Next数组 ";
    print(next);
}

int main()
{
    string s = "bababa";
    string t = "abab";
    testNext(t);
    print(kmp(s, t));
    return 0;
}